Asynchronous Transfer Mode (ATM) is a digital communication standard for transmitting information. In the Asynchronous Transfer Mode system, the information to be transmitted is divided into fifty-three byte units known as "cells." The fifty-three byte cells of information are transmitted from a source node to a destination node through an ATM network constructed of communication lines and ATM switches.
In an ATM system, information is communicated from a source node to a destination node through a defined path known as a "virtual circuit". The virtual circuit is set up when a connection is needed and later torn down when the connection is no longer needed. Each virtual circuit is defined by several parameters such as Quality of Service (QOS) parameters and traffic parameters, the latter of which may include a required bandwidth. Once a virtual circuit has been established, all cells will travel along the same set of intermediary nodes between the source node and the destination node until the virtual circuit is torn down. However, when a subsequent virtual circuit is established between the same source node and destination node, the subsequent virtual circuit may not consist of the same intermediary nodes.
Within each ATM node, the ATM node must switch ATM cells from incoming communication lines to outgoing communication lines. Since a virtual circuit may have a defined required bandwidth amount, the ATM node must carefully schedule cell servicing such that the virtual circuit receives its required bandwidth and QOS requirements. To perform this function, a cell scheduler is implemented for each outgoing communication line. The cell scheduler allocates the bandwidth of its associated communication line to the virtual circuits or groups of virtual circuits that are assigned to use that communication line. Then the cell scheduler must schedule cells from queues associated with each virtual circuit or virtual circuit group such that each receives its allocated bandwidth.